/*
 * To change this template, choose Tools | Templates and open the template in
 * the editor.
 */
package laberinto;

import java.io.*;
import java.util.PriorityQueue;
import java.util.logging.Level;
import java.util.logging.Logger;
import p1fia.MazeHelper;

/**
 *
 * @author asc
 */
public class Laberinto {

    private static class casilla implements java.lang.Comparable
    {
        public casilla(){
            begin=false;
            end=false;
            right=false;
            left=false;
            up=false;
            down=false;
            rute="";
            pValue=Integer.MAX_VALUE;
            gValue=Integer.MAX_VALUE;
            hValue=Integer.MAX_VALUE;
            posX=-1;
            posY=-1;
            anterior=null;
        }

        public casilla getAnterior()
        {
            return anterior;
        }

        public void setAnterior(casilla anterior)
        {
            this.anterior = anterior;
        }

        public Boolean getBegin()
        {
            return begin;
        }

        public void setBegin(Boolean begin)
        {
            this.begin = begin;
        }

        public Boolean getDown()
        {
            return down;
        }

        public void setDown(Boolean down)
        {
            this.down = down;
        }

        public Boolean getEnd()
        {
            return end;
        }

        public void setEnd(Boolean end)
        {
            this.end = end;
        }

        public int getgValue()
        {
            return gValue;
        }

        public void setgValue(int gValue)
        {
            this.gValue = gValue;
        }

        public int gethValue()
        {
            return hValue;
        }

        public void sethValue(int hValue)
        {
            this.hValue = hValue;
        }

        public Boolean getLeft()
        {
            return left;
        }

        public void setLeft(Boolean left)
        {
            this.left = left;
        }

        public int getpValue()
        {
            return pValue;
        }

        public void setpValue(int pValue)
        {
            this.pValue = pValue;
        }

        public int getPosX()
        {
            return posX;
        }

        public void setPosX(int posX)
        {
            this.posX = posX;
        }

        public int getPosY()
        {
            return posY;
        }

        public void setPosY(int posY)
        {
            this.posY = posY;
        }

        public Boolean getRight()
        {
            return right;
        }

        public void setRight(Boolean right)
        {
            this.right = right;
        }

        public String getRute()
        {
            return rute;
        }

        public void setRute(String rute)
        {
            this.rute = rute;
        }

        public Boolean getUp()
        {
            return up;
        }

        public void setUp(Boolean up)
        {
            this.up = up;
        }
        

               
        public String getSolucion(){
            if(begin)return "";
            else if(anterior != null)return anterior.getSolucion() + rute;
            else if(end) return rute;
            else return "!";
        }
        
        public void nodoValue(){
            if(heuristica == 1){
                hValue=Math.abs(posX - data[2]) + Math.abs(posY - data[3]);
            }
            else{
                hValue=(int)Math.sqrt(Math.pow(posX - data[2], 2) + Math.pow(posY - data[3], 2));
            }
            pValue=gValue+hValue;
        }
        
        Boolean begin;
        Boolean end;
        Boolean right;
        Boolean left;
        Boolean up;
        Boolean down;
        String rute;
        int pValue;
        int gValue;
        int hValue;
        int posX;
        int posY;

        @Override
        public boolean equals(Object obj)
        {
            if (obj == null)
            {
                return false;
            }
            if (getClass() != obj.getClass())
            {
                return false;
            }
            final casilla other = (casilla) obj;
            if (this.posX != other.posX)
            {
                return false;
            }
            if (this.posY != other.posY)
            {
                return false;
            }
            return true;
        }

        @Override
        public int hashCode()
        {
            int hash = 7;
            hash = 17 * hash + this.posX;
            hash = 17 * hash + this.posY;
            return hash;
        }

        @Override
        public int compareTo(Object obj)
        { 
            if (obj == null)
            {
                return 0;
            }
            if (getClass() != obj.getClass())
            {
                return 0;
            }
            final casilla other = (casilla) obj;
            if (getpValue() < other.getpValue()){
                //return 1;
                return getpValue() - other.getpValue();
            }
            if(gethValue() < other.gethValue()){
                //return 1;
                return getpValue() - other.getpValue() + gethValue() - other.gethValue();
            }
            if(getgValue() > other.getgValue()){
                //return 1;
                return getpValue() - other.getpValue() + gethValue() - other.gethValue() + getgValue() - other.getgValue();
            }
            
            return Integer.MAX_VALUE;
        }
        
        
        casilla anterior;
        
    }
    
    static int heuristica;
    static casilla[][] tablero;
    static int[] data = new int[4];
    static int[] size = new int[2];
    static int expandidos;
    static int visitados;
    static MazeHelper mzh;
    
    static void parse(String fichero){
        try
        {
            //RandomAccessFile entrada = new RandomAccessFile(fichero,"r");
            BufferedReader entrada = new BufferedReader(new InputStreamReader(new FileInputStream(fichero), "UTF-8"));
            String Tam = entrada.readLine();
            String[] tamanyo = Tam.split("x");
            
            //size[0]=Integer.parseInt(tamanyo[0]);
            size[0]=Integer.parseInt(tamanyo[1]);
            size[1]=Integer.parseInt(tamanyo[1]);
            tablero = new casilla[size[0]][size[1]];

            String linea1 = entrada.readLine();
            String linea2;
            String linea3;
            for (int i = 0; i < size[0]; i++)
            {
                linea2 = entrada.readLine();
                linea3 = entrada.readLine();
                
                for (int j = 0; j < size[1]; j++)
                {
                    tablero[i][j]=new casilla();
                    tablero[i][j].setPosX(i);
                    tablero[i][j].setPosY(j);
                    if(linea1.charAt(2*j+1)=='*'){
                        tablero[i][j].setUp(false);
                    }
                    else{
                        tablero[i][j].setUp(true);
                    }
                    
                    if(linea2.charAt(2*j)=='*'){
                        tablero[i][j].setLeft(false);
                    }
                    else{
                        tablero[i][j].setLeft(true);
                    }
                    
                    if(linea2.charAt(2*j+1)=='S'){
                        data[0]=i;
                        data[1]=j;
                        tablero[i][j].setBegin(true);
                        tablero[i][j].setEnd(false);
                        tablero[i][j].setgValue(0);
                    }
                    else if(linea2.charAt(2*j+1)=='E'){
                        data[2]=i;
                        data[3]=j;
                        tablero[i][j].setEnd(true);
                        tablero[i][j].setBegin(false);
                        tablero[i][j].setRute("!");
                    }
                    else{
                        tablero[i][j].setEnd(false);
                        tablero[i][j].setBegin(false);
                    }
                    
                    if(linea2.charAt(2*j+2)=='*'){
                        tablero[i][j].setRight(false);
                    }
                    else{
                        tablero[i][j].setRight(true);
                    }
                    
                    if(linea3.charAt(2*j+1)=='*'){
                        tablero[i][j].setDown(false);
                    }
                    else{
                        tablero[i][j].setDown(true);
                    }
                    
                    
                }
                linea1=linea3;
            }
        }
        catch (IOException ex)
        {
            Logger.getLogger(Laberinto.class.getName()).log(Level.SEVERE, null, ex);
        }
            
        
    }
    
    public static String SolLaberinto(){
        expandidos=0;
        visitados=0;
        tablero[data[0]][data[1]].nodoValue();
        PriorityQueue<casilla> listaInterior = new PriorityQueue<casilla>();
        PriorityQueue<casilla> listaFrontera = new PriorityQueue<casilla>();
        listaFrontera.offer(tablero[data[0]][data[1]]);
        expandidos++;
        while(!listaFrontera.isEmpty()){
            casilla n = listaFrontera.peek();
            if(listaFrontera.isEmpty())return "!";
            else if(n.getEnd()) return n.getSolucion();
            
            listaFrontera.remove();
            listaInterior.offer(n);
            visitados++;
            
            for (int i = 0; i < 4; i++)
            {
                mzh.setCellInfo(n.getPosX(), n.getPosY(), String.valueOf("P:" + n.getpValue() + "\nG:" + n.getgValue() + "\nH:" + n.gethValue() + "\n"));
                casilla siguiente;
                switch (i){
                    case 0:
                        if(n.getUp()){
                            siguiente=tablero[n.getPosX()-1][n.getPosY()];
                            if(siguiente.getAnterior()!=null){
                                if(siguiente.getgValue() > (n.getgValue() + 1)){
                                    listaFrontera.remove(siguiente);
                                    siguiente.setAnterior(n);
                                    siguiente.setRute("U");
                                    siguiente.setgValue(n.getgValue()+1);
                                    siguiente.nodoValue();
                                    listaFrontera.offer(siguiente);
                                    expandidos++;
                                }
                            }
                            else{
                                if(siguiente.getgValue() > (n.getgValue() + 1)){
                                    siguiente.setAnterior(n);
                                    siguiente.setRute("U");
                                    siguiente.setgValue(n.getgValue()+1);
                                    siguiente.nodoValue();
                                    listaFrontera.offer(siguiente);
                                    expandidos++;
                                }
                            }
                        }
                        break;
                    case 1:
                        if(n.getDown()){
                            siguiente=tablero[n.getPosX()+1][n.getPosY()];
                            if(siguiente.getAnterior()!=null){
                                if(siguiente.getgValue() > (n.getgValue() + 1)){
                                    listaFrontera.remove(siguiente);
                                    siguiente.setAnterior(n);
                                    siguiente.setRute("D");
                                    siguiente.setgValue(n.getgValue()+1);
                                    siguiente.nodoValue();
                                    listaFrontera.offer(siguiente);
                                    expandidos++;
                                }
                            }
                            else{
                                if(siguiente.getgValue() > (n.getgValue() + 1)){
                                    siguiente.setAnterior(n);
                                    siguiente.setRute("D");
                                    siguiente.setgValue(n.getgValue()+1);
                                    siguiente.nodoValue();
                                    listaFrontera.offer(siguiente);
                                    expandidos++;
                                }
                            }
                        }
                        break;
                    case 2:
                        if(n.getRight()){
                            siguiente=tablero[n.getPosX()][n.getPosY()+1];
                            if(siguiente.getAnterior()!=null){
                                if(siguiente.getgValue() > (n.getgValue() + 1)){
                                    listaFrontera.remove(siguiente);
                                    siguiente.setAnterior(n);
                                    siguiente.setRute("R");
                                    siguiente.setgValue(n.getgValue()+1);
                                    siguiente.nodoValue();
                                    listaFrontera.offer(siguiente);
                                    expandidos++;
                                }
                            }
                            else{
                                if(siguiente.getgValue() > (n.getgValue() + 1)){
                                    siguiente.setAnterior(n);
                                    siguiente.setRute("R");
                                    siguiente.setgValue(n.getgValue()+1);
                                    siguiente.nodoValue();
                                    listaFrontera.offer(siguiente);
                                    expandidos++;
                                }
                            }
                        }
                        break;
                    case 3:
                        if(n.getLeft()){
                            siguiente=tablero[n.getPosX()][n.getPosY()-1];
                            if(siguiente.getAnterior()!=null){
                                if(siguiente.getgValue() > (n.getgValue() + 1)){
                                    listaFrontera.remove(siguiente);
                                    siguiente.setAnterior(n);
                                    siguiente.setRute("L");
                                    siguiente.setgValue(n.getgValue()+1);
                                    siguiente.nodoValue();
                                    listaFrontera.offer(siguiente);
                                    expandidos++;
                                }
                            }
                            else{
                                if(siguiente.getgValue() > (n.getgValue() + 1)){
                                    siguiente.setAnterior(n);
                                    siguiente.setRute("L");
                                    siguiente.setgValue(n.getgValue()+1);
                                    siguiente.nodoValue();
                                    listaFrontera.offer(siguiente);
                                    expandidos++;
                                }
                            }
                        }
                        break;
                        
                }
            }
                
                
        }
        return tablero[data[2]][data[3]].getSolucion();
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        heuristica = 0;
        String[] NomFich=args[0].split("=");
        mzh = new MazeHelper();
        mzh.loadFromFile(NomFich[1]);
        parse(NomFich[1]);
        String sol = SolLaberinto();
        System.out.print(sol + "\n");
        System.out.print(String.valueOf(visitados) + "/" + String.valueOf(size[0]*size[1]) + "\n");
            
        if (args.length == 2)
        {
            String[] NomHtml=args[1].split("=");
            if(!sol.equals("!"))mzh.applySolution(sol);
            mzh.saveToFile(NomHtml[1], true); 
        
        }
    }
}
